package Tree;

public class _687_LongestUnivaluePath {
    //wrong answer:this solution can solve the problem that
    //which is the most associated node,which likes nest,not path
    public int longestUnivaluePath_w(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int max = getlength(root.left, root.val) + getlength(root.right, root.val);
            int submax = Math.max(longestUnivaluePath_w(root.left), longestUnivaluePath_w(root.right));
            max = Math.max(submax, max);
            return max;
        }
    }

    public int getlength_w(TreeNode root, int val) {
        int count = 0;
        if (root == null) {
            return count;
        }
        if (root.val == val) {
            count++;
            TreeNode left = root.left;
            TreeNode right = root.right;
            return count + getlength_w(left,root.val) + getlength_w(right,root.val);
        } else {
            return count;
        }
    }

    public int longestUnivaluePath(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int max = getlength(root.left, root.val) + getlength(root.right, root.val);
            int submax = Math.max(longestUnivaluePath(root.left), longestUnivaluePath(root.right));
            return Math.max(max, submax);
        }
    }

    public int getlength(TreeNode root, int val) {
        int count = 0;
        if (root == null) {
            return count;
        }
        if (root.val == val) {
            count++;
            TreeNode left = root.left;
            TreeNode right = root.right;
            return count + Math.max(getlength(left,root.val),getlength(right,root.val));
        } else {
            return count;
        }
    }

}
